use std::cmp::Ordering;

use crate::core::dag_params::AbstractDagParams;
use crate::core::priorityset::{Path, PrioritySet};

// Directed Acyclic Graph（有向无环图）算法实现
pub fn dag<T: AbstractDagParams>(
    dag_params: &T,
    pinyin_list: &[String],
    path_num: usize,
    log: bool,
) -> Vec<Vec<String>> {
    let pinyin_num = pinyin_list.len();
    if pinyin_num == 0 {
        return vec![];
    }

    let mut dynamic_programming_table: Vec<PrioritySet> = (0..pinyin_num)
        .map(|_| PrioritySet::new(path_num))
        .collect();

    for from_idx in 0..1 {
        for to_idx in from_idx..pinyin_num {
            let words = dag_params.get_phrase(&pinyin_list[from_idx..to_idx + 1], path_num);
            for word in words {
                let path = Path::new(
                    vec![word.value.clone()],
                    if log { word.score.ln() } else { word.score },
                );
                dynamic_programming_table[to_idx].put(path);
            }
        }
    }

    for from_idx in 1..pinyin_num {
        let prev_paths = &dynamic_programming_table[from_idx - 1].paths.clone();
        for to_idx in from_idx..pinyin_num {
            let words = dag_params.get_phrase(&pinyin_list[from_idx..to_idx + 1], path_num);
            for prev_path in prev_paths {
                for word in &words {
                    let mut new_words = prev_path.value.clone();
                    new_words.push(word.value.clone());
                    let score: f64 = if log {
                        prev_path.score + word.score.ln()
                    } else {
                        prev_path.score * word.score
                    };
                    dynamic_programming_table[to_idx].put(Path::new(new_words, score));
                }
            }
        }
    }

    let mut result = dynamic_programming_table[dynamic_programming_table.len() - 1]
        .paths
        .iter()
        .map(|path| path)
        .collect::<Vec<&Path>>();

    // 按照分数从大到小排序
    result.sort_by(|a, b| a.partial_cmp(&b).unwrap_or(Ordering::Equal));

    return result.into_iter().map(|item| item.value.clone()).collect();
}
